This invention is in the field of digital data communications, and is more specifically directed to decoding of transmissions that have been coded for error detection and correction.
High-speed data communications, for example in providing high-speed Internet access, is now a widespread utility for many businesses, schools, and homes. At this stage of development, such access is provided according to an array of technologies. Data communications are carried out over existing telephone lines, with relatively slow data rates provided by voice band modems (e.g., according to the current v.92 communications standards), and at higher data rates using Digital Subscriber Line (DSL) technology. Another modern data communications approach involves the use of cable modems communicating over coaxial cable, such as provided in connection with cable television services. The Integrated Services Digital Network (ISDN) is a system of digital phone connections over which data is transmitted simultaneously across the world using end-to-end digital connectivity. Localized wireless network connectivity according to the IEEE 802.11 standard has become very popular for connecting computer workstations and portable computers to a local area network (LAN), and often through the LAN to the Internet. Wireless data communication in the Wide Area Network (WAN) context, which provides cellular-type connectivity for portable and handheld computing devices, is expected to also grow in popularity.
A problem that is common to all data communications technologies is the corruption of data due to noise. As is fundamental in the art, the signal-to-noise ratio for a communications channel is a degree of goodness of the communications carried out over that channel, as it conveys the relative strength of the signal that carries the data (as attenuated over distance and time), to the noise present on that channel. These factors relate directly to the likelihood that a data bit or symbol received over the channel is in error relative to the data bit or symbol as transmitted. This likelihood is reflected by the error probability for the communications over the channel, commonly expressed as the Bit Error Rate (BER) ratio of errored bits to total bits transmitted. In short, the likelihood of error in data communications must be considered in developing a communications technology. Techniques for detecting and correcting errors in the communicated data must be incorporated for the communications technology to be useful.
Error detection and correction techniques are typically implemented through the use of redundant coding of the data. In general, redundant coding inserts data bits into the transmitted data stream that do not add any additional information, but that indicate whether an error is present in the received data stream. More complex codes provide the ability to deduce the true transmitted data from a received data stream, despite the presence of errors.
Many types of redundant codes that provide error correction have been developed. One type of code simply repeats the transmission, for example repeating the payload twice, so that the receiver deduces the transmitted data by applying a decoder that determines the majority vote of the three transmissions for each bit. Of course, this simple redundant approach does not necessarily correct every error, but greatly reduces the payload data rate. In this example, a predictable likelihood remains that two of three bits are in error, resulting in an erroneous majority vote despite the useful data rate having been reduced to one-third. More efficient approaches, such as Hamming codes, have been developed toward the goal of reducing the error rate while maximizing the data rate.
The well-known Shannon limit provides a theoretical bound on the optimization of decoder error as a function of data rate. The Shannon limit provides a metric against which codes can be compared, both in the absolute and relative to one another. Since the time of the Shannon proof, modern data correction codes have been developed to more closely approach the theoretical limit. An important type of these conventional codes are “turbo” codes, which encode the data stream by applying two convolutional encoders. One convolutional encoder encodes the datastream as given, while the other encodes a pseudo-randomly interleaved version of the data stream. The results from the two encoders are interwoven to produce the output encoded data stream.
Another class of known redundant codes is the Low Density Parity Check code. According to this class of codes, a sparse matrix H defines the code, with the encodings, or codewords, c of the payload data satisfying:Hc=0  (1)over Galois field GF(2). Each codeword c consists of the source message s combined with the corresponding parity check bits for that source message s. The encodings c are transmitted, with the receiving network element receiving a signal vector r=c+n, n being the noise added by the channel. Because the decoder at the receiver knows matrix H, it can compute a vector z=Hr. However, because r=c+n, and because Hc=0:z=Hr=Hc+Hn=Hn  (2)The decoding process thus involves finding the sparsest vector x that satisfies the equation:Hx=z  (3)over GF(2). The vector x becomes the best guess for noise vector n, which can be subtracted from the received signal vector r to recover encodings c, from which the original source message s is recoverable. There are many examples of LDPC codes that are known in the art, some of which have been described as providing code performance that approaches the Shannon limit, as described in Tanner et al., “A Class of Group-Structured LDPC Codes”, ISTCA-2001 Proc. (Ambleside, England, 2001).
However, high-performance LDPC code decoders are difficult to implement into hardware. While Shannon's adage holds that random codes are good codes, it is regularity that allows efficient hardware implementation. To address this difficult tradeoff between code irregularity and hardware efficiency, the technique of belief propagation provides an iterative implementation of LDPC decoding that can be made somewhat efficient, as described in Richardson, et al., “Design of Capacity—Approaching Irregular Low-Density Parity Check Codes,” IEEE Trans. on Information Theory, Vol. 47, No. 2 (February 2001), pp. 619–637; and in Zhang et al., “VLSI Implementation-Oriented (3,k)-Regular Low-Density Parity-Check Codes”, IEEE Workshop on Signal Processing Systems (September 2001), pp. 25.–36. Belief propagation decoding algorithms are also referred to in the art as probability propagation algorithms, message passing algorithms, and as sum-product algorithms.
In summary, belief propagation algorithms are based on the binary parity check property of LDPC codes. As mentioned above and as known in the art, each check vertex in the LDPC code constrains its neighboring variables to form a word of even parity. In other words, the product of the correct LDPC code word vector with each row of the parity check matrix sums to zero. According to the belief propagation approach, the received data are used to represent the input probabilities at each input node (also referred to as a “bit node”) of a bipartite graph having input nodes and check nodes. Within each iteration of the belief propagation method, bit probability messages are passed from the input nodes to the check nodes, updated according to the parity check constraint, with the updated values sent back to and summed at the input nodes. The summed inputs are formed into log likelihood ratios (LLRs) defined as:
                              L          ⁡                      (            c            )                          =                  log          ⁡                      (                                          P                ⁡                                  (                                      c                    =                    0                                    )                                                            P                ⁡                                  (                                      c                    =                    1                                    )                                                      )                                              (        4        )            where c is a coded bit received over the channel.
In its conventional implementation, the belief propagation algorithm uses two value arrays, a first array L storing the LLRs for j input nodes, and the second array R storing the results of m parity check node updates, with m being the parity check row index and j being the column (or input node) index of the parity check matrix H. The general operation of this conventional approach determines, in a first step, the R values by estimating, for each check sum (row of the parity check matrix) the probability of the input node value from the other inputs used in that checksum. The second step of this algorithm determines the LLR probability values of array L by combining, for each column, the R values for that input node from parity check matrix rows in which that input node participated. A “hard” decision is then made from the resulting probability values, and is applied to the parity check matrix. This two-step iterative approach is repeated until the parity check matrix is satisfied (all parity check rows equal zero, GF(2)), or until another convergence criteria is reached, or a terminal number of iterations have been executed.
By way of further background, the code design approach described in Boutillon et al., “Decoder-First Code Design”, Proc.: Int'l Symp. on Turbo Codes and Related Topics (Brest, France, September 2001) defines the decoder architecture first, and uses this architecture to constrain the design of the LDPC code itself. Sridhara, et al., “Low Density Parity Check Codes from Permutation Matrices”, 2001 Conference on Information Sciences and Systems (Johns Hopkins University, Mar. 21–23, 2001) describes the LDPC code as constructed from shifted identity matrices (i.e., permutation matrices).
However, it has been observed that these prior approaches are somewhat limited, in that these approaches are limited to a single code or a small selection of codes. Practically useful communications receivers require some amount of flexibility in code rates, and in optimizing their operation for varying noise levels and channel conditions. As a result of this observation, my copending and commonly assigned application Ser. No. 10/329,597 filed Dec. 26, 2002, published as U.S. Patent Application Publication No. US 2004/0034828 A1, and incorporated herein by this reference describes a low density parity check (LDPC) code that is particularly well adapted for efficient hardware implementation in a belief propagation decoder circuit. As described in this copending application, the LDPC code is arranged as a macro matrix whose rows and columns represent block columns and block rows of a corresponding parity check matrix. Each non-zero entry corresponds to a permutation matrix, such as a cyclically shifted identity matrix, with the shift corresponding to the position of the permutation matrix entry in the macro matrix. The block columns of the macro matrix are grouped, so that only one column in the macro matrix group contributes to the parity check sum in any given row. The decoder circuitry includes a parity check value estimate memory which may be arranged in banks that can be logically connected in various data widths and depths. A parallel adder generates extrinsic estimates that are applied to parity check update circuitry for generating new parity check value estimates. These parity check value estimates are stored back into the memory, and are forwarded to bit update circuits for updating of probability values for the input nodes.
By way of further background, my copending and commonly assigned application Ser. No. 10/724,280, filed Nov. 28, 2003 published as U.S. Patent Application Publication No. US 2004/0148560, and incorporated herein by this reference, describes encoder circuitry for applying a low-density parity check (LDPC) code, such as that described in the above-referenced Patent Application Publication US 2004/0034828 A1, to information words to be transmitted.
By way of still further background, Li et al., “Generalized Product Accumulate Codes: Analysis and Performance”, Global Communications Conference (Globecomm) (IEEE, 2001), pp. 975–79, describe a layered approach to the outer code of product accumulate codes. It is observed that these outer codes (referred to in the paper as “turbo” product codes) are layered LDPC codes, with each layer decoded by way of belief propagation. It is also observed that, because the column weight in each layer is at most one, only a single iteration is possible within each layer.
By way of still further background, Mansour, et al., “Turbo decoder architectures for low-density parity check codes”, Global Communications Conference (Globecomm) (IEEE, 2002), pp. 1383–88; and Mansour, et al., “On the Architecture-Aware Structure of LDPC Codes from Generalized Ramanujan Graphs and their Decoder Architectures”, 2003 Conference on Information Sciences and Systems (Johns Hopkins University, Mar. 12, 2002), also describe a layered, or “turbo”, approach for LDPC decoding. In these articles, the LDPC parity check matrices are block partitioned into columns and rows, with a maximum column weight of one in each layer. These articles assert that the layered approach reduces the number of iterations necessary for decoding, relative to belief propagation decoding that does not use layered decoding.